Efficient Algorithms for Residual Connectedness Reliability of the Distributed Systems Zhongshi He and Yinong Chen Highly Dependable Systems Research Programme University of the Witwatersrand , Johannesburg, South Africa {zhe, yinong }@cs.wits.ac.za http://www.cs.wits.ac.za/research/programme.html Full Paper in Postscript File Abstract This paper discusses the reliability of a distributed system in which the links are considered reliable while the computing nodes may fail with certain probability. We need to find a subset of nodes in the system to run replicas of a critical task so that the task can survive as long as possible. The system configuration can be changed due to nodes' failures and task reallocation (system reconfiguration) has to be performed after a number of nodes become faulty. The task reallocation problem is converted into a well-known graph theory problem and the reliability of a task is modelled by the residual connectedness reliability R(G) of a graph G. To perform optimal task reallocation, we need to calculate R(G) after a number of nodes become faulty. This paper proposes a new approach with efficient algorithms for evaluating R(G). Numerical and graphic results are presented. Key words. network reliability, bounds, connectedness, distributed system, hypercube.